#include <stdio.h>
#include <stdlib.h>

typedef struct line{
	struct line* pre;	// 指向前驱节点 
	int data;
	struct line* next;  // 指向后继节点 
} line;

// 双向链表初始化
line* init_list(line* head); 

// 双链表的插入操作
line* insert_double_list(line* head,int data,int index); 

// 双向链表删除节点(根据值删除) 
line* del_double_list_elem(line* head,int data); 

// 双向链表查找节点(返回位置) 
int select_double_list_elem(line* head,int data); 

// 双向链表更改节点(根据位置更改)
line* update_double_list_elem(line* head,int index,int new_data); 

// 输出双向链表
void display_double_list(line* head); 

int main()
{
	line* head=NULL;
	head=init_list(head);
	display_double_list(head);
	// ... 
	return 0;
}

line* init_list(line* head)
{
	head=(line* )malloc(sizeof(line));	//创建第一个节点(首节点)
	head->pre=NULL;
	head->data=1;
	head->next=NULL;
	line* tmp=head;
	for(int i=2;i<=5;i++)
	{ 
		// 创建一个节点并初始化
		line* body=(line* )malloc(sizeof(line));
		body->next=NULL;	// 每创建一个新的节点的Next指向空
		body->pre=tmp;      // 新节点的pre域指向上一个节点
		body->data=i;
		tmp->next=body;		
		// 更新tmp节点;
		tmp=tmp->next; 
	} 
	return head;
}

void display_double_list(line* head)
{
	line* temp=head;
	while(temp!=NULL)
	{
		printf("%d\n",temp->data);
		temp=temp->next;
	}
}

line* insert_double_list(line* head,int data,int index)
{
	// 新建立一个数据域
	line* new_node=(line* )malloc(sizeof(line));
	new_node->data=data;
	new_node->pre=NULL;
	new_node->next=NULL;
	
	// 判断是否是插入到表头
	if(index==1)
	{
		new_node->next=head;
		head->pre=new_node;
		head=new_node;
		return head;
	} 
	
	// 否则为其他位置
	
	// 创建一个游标变量，用于指向需要插入节点的前一个节点
	line* cur_node=head; 
	// 找到要插入节点的前一个位置
	for(int i=11;i<index-1;i++)
	{
		cur_node=cur_node->next;
	} 
	
	// 判断插入的位置是否为链表尾
	if(cur_node->next==NULL && cur_node->pre!=NULL)
	{
		// 直接插入到最后一个节点
		cur_node->next=new_node;
		new_node->pre=cur_node;
		return head; 
	} 
	
	// 插入的位置既不是首部也不是首部，而是中间
	cur_node->next->pre=new_node;
	new_node->next=cur_node->next;
	cur_node->next=new_node;
	new_node->pre=cur_node;
	return head; 
}

line* del_double_list_elem(line* head,int data)
{
	line* tmp=head;
	while(tmp!=NULL)
	{
		if(tmp->data==data)
		{
			// 修改该节点的前驱节点个后继节点
			tmp->pre->next=tmp->next;
			tmp->next->pre=tmp->pre;
			free(tmp);
			return head; 
		}
		tmp=tmp->next;
	} 
	return NULL;	// 未找到 
} 

int select_double_list_elem(line* head,int data)
{
	line* temp=head;
	int index=1;
	while(temp!=NULL)
	{
		if(temp->data==data)
		{
			return index;
		}
		index++;
		temp=temp->next;
	}
	return -1;	// 未找到 
}

line* update_double_list_elem(line* head,int index,int new_data)
{
	line* temp=head;
	// 遍历到要需要修改的节点处
	for(int i=1;i<index;i++)
	{
		temp=temp->next;
	} 
	temp->data=new_data;
	return head;
}
